/**
 * 给定一个N位数，例如12345，从里面去掉k个数字，得到一个N-k位的数，
 * 例如去掉2，4，得到135，去掉1，5，得到234。
 * 设计算法，求出所有得到的N-k位数里面最小的那一个?
 */
function getMin (arr, k){
  let minArr = [];
  const q = []

  for(let i = 0; i < arr.length; i++) {
    while(q.length && arr[i] < q[q.length - 1]) q.pop();
    q.push(arr[i]);

    if(minArr.length < k) { 
      minArr.push(arr[i]);
    } else {
      minArr = minArr.slice(0, -q.length).concat(q);
    }
  }
  return minArr.slice(0, k).join('');
}

// 动归
// f(n, k): 从个数中挑选k位
// f(n, k) = min(f(n-1, k), f(n-1, k-1) + arr[i]);
function getMin2 (arr, k){
  if(arr.length < k) return arr.join('');
  // 可替换为滚动数组
  let temp = [];
  for (let i = 0; i <= arr.length; i++) {
    temp.push([]);
  }

  for (let i = 1; i <= arr.length; i++) {
    for (let j = 1; j <= i; j++) {
      if(i === 1) {
        temp[i][j] = arr[i - 1] + '';
        continue;
      }
      if(j === 1) {
        temp[i][j] = Math.min(temp[i - 1][j], arr[i - 1]) + '';
        continue;
      }
      if(i === j) {
        temp[i][j] = temp[i - 1][j - 1] + arr[i - 1] + '';
        continue;
      } 

      // 不选择 i
      let val1 = temp[i - 1][j];
      // 选择 i
      let val2 = temp[i - 1][j - 1] + '' + arr[i - 1];
      temp[i][j] = Math.min(val1, val2) + '';
    }
  }
  return temp[arr.length][k];
}

// let arr = [3, 5, 1, 2, 6, 9, 8];
// let arr = [1, 3, 8, 2, 4, 9, 5];
// let arr = [1,3,5,2,4,7];
let arr = [1,4,3,2,2,1,9];
let result1 = getMin(arr, 4);
let result2 = getMin2(arr, 4);
console.log(result1, result2);


